#include <iostream>
#include <vector>
#include <stack>
#include <Vector.hpp>

using namespace std;
class Solution
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites)
    {
        stack<int> stack;
        vector<vector<int>> graph(numCourses);
        vector<int> visited(numCourses, 0); // 0 unvisited,1 visited,2 visited and in stack
        for (auto edge : prerequisites)
        {
            graph[edge[1]].push_back(edge[0]);
        }
        for (int i = 0; i < numCourses; i++)
        {
            if (visited[i] == 0)
            {
                if (!dfs(graph, visited, stack, i))
                {
                    return vector<int>();
                }
            }
        }
        vector<int> res;
        while (!stack.empty())
        {
            res.push_back(stack.top());
            stack.pop();
        }
        return res;
    }

    bool dfs(vector<vector<int>> &graph, vector<int> &visited, stack<int> &stack, int index)
    {
        if (visited[index] == 1)
            return false;
        if (visited[index] == 2)
            return true;
        visited[index] = 1;
        for (auto out : graph[index])
        {
            if (!dfs(graph, visited, stack, out))
            {
                return false;
            }
        }
        stack.push(index);
        visited[index] = 2;
        return true;
    }
};

int main()
{
    cout << "Code210" << endl;
    Solution s;
    vector<vector<int>> prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
    vector<int> res = s.findOrder(4, prerequisites);
    PrintVector(res);
    return 0;
}

/*
vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites)
{
    vector<int> res;
    map<int, pair<int, vector<int>>> degrees; // index,in,out
    for (int i = 0; i < numCourses; i++)
    {
        degrees[i] = {0, {}};
    }
    for (int i = 0; i < prerequisites.size(); i++)
    {
        int from = prerequisites[i][1];
        int to = prerequisites[i][0];
        degrees[to].first++;
        degrees[from].second.push_back(to);
    }
    stack<int> zeroStack;
    for (auto it = degrees.begin(); it != degrees.end(); it++)
    {
        if (it->second.first == 0)
        {
            zeroStack.push(it->first);
        }
    }
    while (!zeroStack.empty())
    {
        int cur = zeroStack.top();
        zeroStack.pop();
        res.push_back(cur);
        for (auto out : degrees[cur].second)
        {
            degrees[out].first--;
            if (degrees[out].first == 0)
            {
                zeroStack.push(out);
            }
        }
    }
    if (res.size() != numCourses)
    {
        res.clear();
    }
    return res;
}
*/